#ifndef __DATA_H__
#define __DATA_H__
#define DATAHEADSIZ 1024
#define DATAMETASIZ 128
#define DATAFASIZ (DATAHEADSIZ-DATAMETASIZ)
#define DATAMAPSIZ (64*1024*1024)
#define DATAMAXAREAMISS 512
#define DATAMAXAREA 10
#define DATAMAGIC 0x1f2e3d4c
#pragma pack(1)
struct area{
    uint64 start;
	int32 length;
	struct area *next;
	//struct area *pre;
};
struct areahead{
    uint64 pre;
	uint64 next;
	int32 siz;
};
struct datahead{
    uint32 magic;
    int32 nrec;
	uint64 filesiz;
	uint64 tail;
	uint64 head;
	uint64 areahd;
	uint64 areatail;
	int32 areanum;
};
struct datafile{
   char *filename;
   int fd;
   int nrec;
   uint64 filesiz;
   uint64 tail;//rec tail
   uint64 head;//rec head
   uint64 mapsiz;
   void *mapaddr;
   uint64 iter;
#define DF_ITER_LAST  1
#define DF_ITER_START 0
   struct area *arealist;
   struct area *arealisttail;
   struct area *areafreelist;
#define ORDER_UNKOWN 0
#define ORDER_START  1
#define ORDER_LENGTH 2
   uchar ordertype;
   int arealen;//current in mem area
   int areanum;//total in file
   uint64 areanext;//next to read
   uint64 areatail;//free area tail
   uint64 areahd;//free area head
   int areamiss;//get area miss
   int areamerge;//area defragement times
   struct reccache *rc;
};
struct datarecord{
   //uchar flag;
   int32 siz;
   int32 rsiz;
   uint64 pre;
   uint64 next;
   //int32 ksiz;
   //int32 vsiz;
};
struct areaitem{
   uint64 start;
   int length;
};
struct areaheap{
   int max;
   int len;
   uchar sorted;
   struct areaitem *array;
};
struct datafile *dataopen(char *name,int flag);
uint64 dataput(struct datafile *df,char *key,int ksiz,char *val,int vsiz);
uint64 dataputrec(struct datafile *df,char *data,int dsiz);
int dataget(struct datafile *df,uint64 offset,struct bstring **val);
int dataerase(struct datafile *df,uint64 offset);
int dataiter_init(struct datafile *df,uint64 offset);
int dataiter_next(struct datafile *df,struct bstring **key,struct bstring **val);
int dataiter_pre(struct datafile *df,struct bstring **key,struct bstring **val);
int dataclose(struct datafile *df);

static struct areaheap* areaheapnew(int n){
   struct areaheap *ap=malloc(sizeof(struct areaheap));
   ap->max=n;
   ap->len=0;
   ap->sorted=0;
   ap->array=n<=0?NULL:malloc(n*sizeof(struct areaitem));
   return ap;
}
static void apsort(struct areaheap *ap){
    if(ap->len<=1) return;
	int i=ap->len>>1;
	struct areaitem ai;
	while(i>0){
	    int j=i;
		int k=ap->len>>1;
		while(j<=k){
		    int p=j;
			j<<=1;
		    if(j<ap->len&&ap->array[j-1].start>ap->array[j].start) j++;
			if(ap->array[j-1].start>ap->array[p-1].start){
			    memcpy(&ai,&ap->array[p-1],sizeof(struct areaitem));
				memcpy(&ap->array[p-1],&ap->array[j-1],sizeof(struct areaitem));
				memcpy(&ap->array[j-1],&ai,sizeof(struct areaitem));
			}else break;
		}
		i--;
	}
}
static int apput(struct areaheap *ap,uint64 start,int len){
    if(ap->sorted==0){
	    if(ap->len==ap->max){
		    apsort(ap);
			ap->sorted=1;
		}else{
		    ap->array[ap->len].start=start;
			ap->array[ap->len].length=len;
			ap->len++;
			return ap->len;
		}
	}
	if(ap->array[0].start>start){
	    int i=1,c;
		struct areaitem ai;
		ap->array[0].start=start;
		ap->array[0].length=len;
		while(i<=(ap->len)>>1){
		    c=i<<1;
			if(c<ap->len&&ap->array[c-1].start<ap->array[c].start) c++;
			if(ap->array[c-1].start>ap->array[i-1].start){
			    memcpy(&ai,&ap->array[i-1],sizeof(struct areaitem));
				memcpy(&ap->array[i-1],&ap->array[c-1],sizeof(struct areaitem));
				memcpy(&ap->array[i-1],&ai,sizeof(struct areaitem));
				i=c;
			}else break;
		}
	}
	return ap->len;
}
static void apsortall(struct areaheap *ap){
    if(ap->len<=1) return;
	if(ap->sorted!=1){
	    apsort(ap);
		ap->sorted=1;
	}
	struct areaitem ai;
	int i=ap->len,p;
	while(i>1){
	    i--;
		memcpy(&ai,&ap->array[0],sizeof(struct areaitem));
	    memcpy(&ap->array[0],&ap->array[ap->len-1],sizeof(struct areaitem));
	    memcpy(&ap->array[ap->len-1],&ai,sizeof(struct areaitem));
		int j=1;
		int k=i>>1;
		while(j<=k){
		    p=j;
			j<<=1;
			if(j<i&&ap->array[j-1].start<ap->array[j].start) j++;
			if(ap->array[j-1].start>ap->array[p-1].start){
			    memcpy(&ai,&ap->array[j-1],sizeof(struct areaitem));
	            memcpy(&ap->array[j-1],&ap->array[p-1],sizeof(struct areaitem));
	            memcpy(&ap->array[p-1],&ai,sizeof(struct areaitem));
			}else break;
		}
	}
}
static void apmerge(struct areaheap *ap){
    if(ap->len<=1) return;
	int i=1,base=0;
	while(i<ap->len){
	    while(i<ap->len&&ap->array[base].start+ap->array[base].length==ap->array[i].start){
		    ap->array[base].length+=ap->array[i].length;
			i++;
		}
		if(i>base&&i<ap->len){
		    memcpy(&ap->array[base+1],&ap->array[i],sizeof(struct areaitem));
		}
		base=i;
	}
	ap->len=base;
}
static void apfree(struct areaheap *ap){
    if(ap->array!=NULL) free(ap->array);
	free(ap);
}
static void apclear(struct areaheap *ap){
    ap->len=0;
}
#endif